(* Generate the combinations of K distinct objects chosen from the N elements of a list. *)

(* This is actually fairly easy in prolog (the original language for the problem), but it gets
   a little bit harder for OCaml. The code below can be understood as an imperative traversal,
   which uses a provided 'emit' function to emit all possible lists of size k. *)

(* 递归函数：从列表list中提取所有长度为k的子序列 *)
let rec extract k list =
  (* 基线条件1：当k<=0时返回包含空列表的列表 *)
  if k <= 0 then [ [] ]
  (* 当k>0时的处理 *)
  else match list with
       (* 基线条件2：输入列表为空时返回空列表 *)
       | [] -> []
       (* 递归情况：分解为头元素h和剩余列表t *)
       | h :: t ->
          (* 递归获取包含h的组合：对剩余列表取k-1长度的组合，每个组合前添加h *)
          let with_h = List.map (fun l -> h :: l) (extract (k-1) t) in
          (* 递归获取不包含h的组合：直接对剩余列表取k长度的组合 *)
          let without_h = extract k t in
          (* 合并两种情况的组合结果 *)
          with_h @ without_h;;


assert (extract 2 [`a;`b;`c;`d] = [[`c;`d]; [`b;`d]; [`b;`c]; [`a;`d]; [`a;`c]; [`a;`b]]) ;;
